#include <stdio.h>
#include <string>
#include <cstring>
#include <tuple>

constexpr int len = 8;
constexpr int array[len] = {5, 4, 7, 1, 3, 5, 2, 6};

void printArray(const std::string &prefix, const int *arr, const int size)
{
    printf("%s", prefix.c_str());
    for (int i = 0; i < size; i++)
    {
        if (i == size - 1)
        {
            printf("%d\n", arr[i]);
        }
        else
        {
            printf("%d, ", arr[i]);
        }
    }
}

void merge_array(int *input, int mid, int length, int *workspace)
{
    int i = 0;
    int j = mid;
    int index = 0;
    while (i < mid && j < length)
    {
        if (input[i] <= input[j])
        {
            workspace[index++] = input[i++];
        }
        else
        {
            workspace[index++] = input[j++];
        }
    }

    while (i < mid)
    {
        workspace[index++] = input[i++];
    }

    while (j < length)
    {
        workspace[index++] = input[j++];
    }
    memcpy(input, workspace, length * sizeof(int));
}

void merge_sort(int *input, int length, int *workspace)
{
    if (length > 1)
    {
        int mid = length / 2;
        merge_sort(input, mid, workspace);
        merge_sort(&input[mid], length - mid, &workspace[mid]);
        merge_array(input, mid, length, workspace);
    }
}

void swap(int &left, int &right)
{
    int temp = left;
    left = right;
    right = temp;
}

void bubble_sort(int *input, int length)
{
    do
    {
        for (int i = 0; i < length - 1; i++)
        {
            if (input[i] > input[i + 1])
            {
                swap(input[i], input[i + 1]);
            }
        }
    } while (length-- > 1);
}

void insert_sort(int *input, int length)
{
    int k = 1;
    do
    {
        for (int i = 0; i < k; i++)
        {
            if (input[k] < input[i])
            {
                swap(input[k], input[i]);
            }
        }
    } while (++k < length);
}

void quick_sort(int *input, int left, int right)
{
    if (left >= right)
        return;
    int l = left, r = right;
    int key = input[l];
    while (l < r)
    {
        while (input[r] >= key && l < r)
            r--;
        if (l < r)
            input[l] = input[r];
        while (input[l] < key && l < r)
            l++;
        if (l < r)
            input[r] = input[l];
    }

    input[l] = key;
    quick_sort(input, left, l - 1);
    quick_sort(input, r + 1, right);
}

void quick_sort(int *input, int length)
{
    quick_sort(input, 0, length - 1);
}

void select_sort(int *input, int length)
{
    int max_idx = 0;
    do
    {
        for (int i = 0; i < length; i++)
        {
            if (input[max_idx] < input[i])
            {
                max_idx = i;
            }
        }
        swap(input[max_idx], input[length - 1]);
    } while (--length > 1);
}

void shell_sort(int *input, int length)
{
    for (int gap = length / 2; gap >= 1; gap /= 2)
    {
        for (int k = 0; k < gap; k++)
        {
            for (int i = gap + k; i < length; i += gap)
            {
                if (input[i] < input[i - gap])
                {
                    swap(input[i], input[i - gap]);
                }
            }
        }
    }
}

int get_max_depth(int *input, int length)
{
    int max = input[0];
    for (int i = 0; i < length; i++)
    {
        max = max < input[i] ? input[i] : max;
    }

    int digit = 1;

    while (max / 10 != 0)
    {
        max /= 10;
        ++digit;
    }

    return digit;
}

void radix_sort_LSD(int *input, int length)
{
    int *ws = (int *)malloc(length * sizeof(int));
    int count[10] = {0};

    int digit = get_max_depth(input, length);

    int base = 1;
    for (int d = 0; d < digit; d++)
    {
        memset(count, 0, 10 * sizeof(int));
        for (int i = 0; i < length; i++)
        {
            int val = (input[i] / base) % 10;
            count[val]++;
        }
        // 求不同分组的边界
        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

        for (int i = length - 1; i >= 0; i--)
        {
            int val = (input[i] / base) % 10;
            int index = count[val];
            ws[index - 1] = input[i];
            count[val]--;
        }
        memcpy(input, ws, length * sizeof(int));

        base *= 10;
    }
    free(ws);
}

void radix_sort_MSD(int *input, int start, int length, int base)
{
    if (base < 1)
        return;

    int count[10] = {0};
    int index[10] = {0};
    int *ws = (int *)malloc(length * sizeof(int));

    for (int i = 0; i < length; i++)
    {
        int val = input[i + start] / base % 10;
        count[val]++;
    }

    memcpy(index, count, 10 * sizeof(int));

    for (int i = 1; i < 10; i++)
    {
        index[i] += index[i - 1];
    }

    for (int i = 0; i < length; i++)
    {
        int val = input[i + start] / base % 10;
        int idx = index[val];
        ws[idx - 1] = input[i + start];
        index[val]--;
    }

    memcpy(&input[start], ws, length * sizeof(int));

    for (int i = 0; i < 10; i++)
    {
        if (count[i] > 1)
        {
            radix_sort_MSD(input, i >= 1 ? index[i - 1] : 0, count[i], base / 10);
        }
    }

    free(ws);
}

void radix_sort_MSD(int *input, int length)
{
    int count[10] = {0};

    int digit = get_max_depth(input, length);

    int base = 1;
    while (digit-- > 1)
    {
        base *= 10;
    }

    radix_sort_MSD(input, 0, length, base);
}

void big_heap_adjust(int *input, int node, int length)
{
    int index = node;
    int child = 2 * index + 1;
    while (child < length)
    {
        if (child + 1 < length && input[child] < input[child + 1])
        {
            child++;
        }
        if (input[index] >= input[child])
        {
            break;
        }

        swap(input[index], input[child]);
        index = child;
        child = 2 * index + 1;
    }
}

void make_big_head(int *input, int length)
{
    for (int i = length / 2; i >= 0; i--)
    {
        big_heap_adjust(input, i, length);
    }
}

void heap_sort(int *input, int length)
{
    make_big_heap(input, length);
    while (length-- > 1)
    {
        swap(input[0], input[length]);
        big_heap_adjust(input, 0, length);
    };
}

std::tuple<int, int> get_min_max(int *input, int length)
{
    int min = INT32_MAX;
    int max = INT32_MIN;

    for (int i = 0; i < length; i++)
    {
        if (max < input[i])
        {
            max = input[i];
        }
        if (min > input[i])
        {
            min = input[i];
        }
    }

    return std::make_tuple(min, max);
}

void count_sort(int *input, int length)
{
    auto [min, max] = get_min_max(input, length);

    int *count = (int *)malloc((max - min + 1) * sizeof(int));
    int *ws = (int *)malloc(length * sizeof(int));
    memset(count, 0, (max - min + 1) * sizeof(int));
    for (int i = 0; i < length; i++)
    {
        count[input[i] - min]++;
    }
    for (int i = 1; i < max - min + 1; i++)
    {
        count[i] += count[i - 1];
    }

    for (int i = 0; i < length; i++)
    {
        int index = input[i] - min;
        ws[count[index] - 1] = input[i];
        count[index]--;
    }
    memcpy(input, ws, length * sizeof(int));
    free(count);
    free(ws);
}

void bucket_sort(int *input, int length)
{
    auto [min, max] = get_min_max(input, length);
    int temp_len = max - min + 1;
    int *count = (int *)malloc(temp_len * sizeof(int));
    memset(count, 0, temp_len * sizeof(int));
    for (int i = 0; i < length; i++)
    {
        count[input[i] - min]++;
    }

    for (int i = 0, j = 0; i < temp_len; i++)
    {
        while (count[i] != 0)
        {
            input[j] = i + min;
            j++;
            count[i]--;
        }
    }
}

int main(int argv, char **argc)
{
    int workspace[len] = {0};
    printArray("原始数据: ", array, len);
    int input[len] = {0};
    memcpy(input, array, len * sizeof(int));
    merge_sort(input, len, workspace);
    printArray("合并排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    bubble_sort(input, len);
    printArray("冒泡排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    insert_sort(input, len);
    printArray("插入排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    quick_sort(input, len);
    printArray("快速排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    select_sort(input, len);
    printArray("选择排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    shell_sort(input, len);
    printArray("希尔排序: ", input, len);
    int new_arr[10] = {50, 30, 0, 100, 11, 2, 123, 543, 187, 49};
    radix_sort_LSD(new_arr, 10);
    printArray("基数排序(LSD): ", new_arr, 10);
    int new_arr1[10] = {50, 30, 0, 100, 11, 2, 123, 543, 187, 49};
    radix_sort_MSD(new_arr1, 10);
    printArray("基数排序(MSD): ", new_arr1, 10);
    memcpy(input, array, len * sizeof(int));
    heap_sort(input, len);
    printArray("堆排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    count_sort(input, len);
    printArray("计数排序: ", input, len);
    memcpy(input, array, len * sizeof(int));
    bucket_sort(input, len);
    printArray("桶排序: ", input, len);
    return 0;
}
